package com.yeung.exam;

public class 割绳子 {
    public static void main(String[] args) {
        System.out.println(cutRope(6));
        System.out.println(cutRope2(7));
    }

    /**
     * 动态规划 O(nlogn)
     *
     * @param target
     * @return
     */
    public static int cutRope(int target) {
        if (target < 2) return 0;
        if (target == 2) return 1;
        if (target == 3) return 2;
        int[] products = new int[target + 1];
        products[0] = 0;
        products[1] = 1;
        products[2] = 2;//此处的结果 是中间结果,并不是说2的情况
        products[3] = 3;
        //因为＜3的情况都可以直接返回
        for (int i = 4; i <= target; i++) {//一个自底向上的计算过程
            int max = 0;
            for (int k = 1; k <= i / 2; k++) {
                int pro = products[k] * products[i - k];//每一种组合情况的计算, 如 i=7 那么有(1*6,2*5,3*4) 而5,6,4 在之前都已经算出结果了
                if (max < pro)
                    max = pro;
            }
            products[i] = max;
        }
        return products[target];
    }

    /**
     * 比动态规划更快,O(longn)
     * * 4 ： 2*2
     * * 5 ： 2*3
     * * 6 ： 3*3
     * * 7 ： 2*2*3 或者4*3
     * * 8 ： 2*3*3
     * * 9 ： 3*3*3
     * * 10：2*2*3*3 或者4*3*3
     * * 11：2*3*3*3
     * * 12：3*3*3*3
     * * 13：2*2*3*3*3 或者4*3*3*3
     * *
     * * 下面是分析：
     * * 首先判断k[0]到k[m]可能有哪些数字，实际上只可能是2或者3。
     * * 当然也可能有4，但是4=2*2，我们就简单些不考虑了。
     * * 5<2*3,6<3*3,比6更大的数字我们就更不用考虑了，肯定要继续分。
     * * 其次看2和3的数量，2的数量肯定小于3个，为什么呢？因为2*2*2<3*3，那么题目就简单了。
     * * 直接用n除以3，根据得到的余数判断是一个2还是两个2还是没有2就行了。
     * * 由于题目规定m>1，所以2只能是1*1，3只能是2*1，这两个特殊情况直接返回就行了。
     *
     * @param target
     * @return
     */
    public static int cutRope2(int target) {
        if (target < 2) return 0;
        if (target == 2) return 1;
        if (target == 3) return 2;
        int x = target % 3;
        int y = target / 3;
        if (x == 0) {
            //直接用3组合会得到最大值
            return (int) Math.pow(3, y);
        } else if (x == 1) {
            return (int) (2 * 2 * Math.pow(3, y - 1));
        } else {
            return (int) (2 * Math.pow(3, y));
        }
    }
}
